package cn.xiaolang.function.data_structure;

/**
 * 数组中心索引
 * <p>
 * 我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
 * 如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个
 * </p>
 *
 * @author fuhw/Dean
 * @date 2020-03-26
 */
public class ArrayPivotIndex {

    public static void main(String[] args) {
        int[] nums = {-1, -1, -1, 0, 1, 1};
        System.out.println(pivotIndex(nums));
    }

    /**
     * 思路：
     * 把数组元素分成三部分：左边元素和，中心索引，右边元素和，满足左边元素和等于右边元素和
     *
     * @param nums 指定数组
     * @return 返回数组的中心索引
     */
    public static int pivotIndex(int[] nums) {
        int sumTotal = 0;
        int sumLeft = 0;
        int sumRight = 0;
        for (int n : nums) {
            sumTotal += n;
        }

        for (int i = 0; i < nums.length; i++) {
            if (i != 0) {
                sumLeft += nums[i - 1];
            }
            sumRight = sumTotal - sumLeft - nums[i];
            if (sumLeft == sumRight) {
                return i;
            }
        }

        return -1;
    }
}
